package common

import java.util.*
import kotlin.collections.ArrayList

//class TreeNode(var `val`: Int) {
    //    var left: TreeNode? = null
//    var right: TreeNode? = null
//}
// 层级遍历
fun printLevelOrder(root: TreeNode?): ArrayList<ArrayList<Int>> {
    // S - N
    // T - N
    val result: ArrayList<ArrayList<Int>> = ArrayList<ArrayList<Int>>()
    if (null == root) {
        return result
    }

    var size: Int
    val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
    queue.offer(root)
    while (!queue.isEmpty()) {
        size = queue.size
        val list: ArrayList<Int> = ArrayList<Int>()
        while (size-- > 0) {
            val node: TreeNode = queue.poll()
            list.add(node.`val`)
            node.left?.let {
                queue.offer(it)
            }
            node.right?.let {
                queue.offer(it)
            }
        }
        result.add(list)
    }
    return result
}

// 层级遍历
fun printLevelOrder2(root: TreeNode?): ArrayList<Int?> {
    // S - N
    // T - N
    val result: ArrayList<Int?> = ArrayList()
    if (null == root) {
        return result
    }

    var size: Int
    val queue: LinkedList<TreeNode?> = LinkedList()
    queue.offer(root)
    while (!queue.isEmpty()) {
        size = queue.size
        while (size-- > 0) {
            val node: TreeNode? = queue.poll()
            result.add(node?.`val`)
            if (null != node && (node.left != null || node.right != null)) {
                queue.offer(node.left)
                queue.offer(node.right)
            }
        }
    }
    if (result.last() == null) {
        result.removeLast()
    }
    return result
}

// 层级遍历
fun printLevelOrder3(root: TreeNode?): ArrayList<Int?> {
    // S - N
    // T - N
    val result: ArrayList<Int?> = ArrayList()
    if (null == root) {
        return result
    }

    var size: Int
    val queue: LinkedList<TreeNode?> = LinkedList()
    queue.offer(root)
    while (!queue.isEmpty()) {
        size = queue.size
        while (size-- > 0) {
            val node: TreeNode? = queue.poll()
            if (null == node) {
                result.add(null)
            } else {
                result.add(node.`val`)
//                if (node.left != null || node.right != null) {
                queue.offer(node.left)
                queue.offer(node.right)
//                }
            }
        }
    }
    while (result.last() == null) {
        result.removeLast()
    }
    return result
}


fun printInorder(root: TreeNode?): List<Int> {
    val result: ArrayList<Int> = ArrayList<Int>()
    if (null == root) {
        return result
    }
    // 中序遍历：左中右
    // Stack : 右中左
    val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
    stack.push(Pair<TreeNode, Boolean>(root, false))

    while (!stack.isEmpty()) {
        val pair: Pair<TreeNode, Boolean> = stack.pop()
        val node = pair.first
        val visited = pair.second
        if (visited) {
            result.add(node.`val`)
            continue
        }
        node.right?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
        stack.push(Pair<TreeNode, Boolean>(node, true))
        node.left?.let { stack.push(Pair<TreeNode, Boolean>(it, false)) }
    }
    return result
}